package cn.edu.jxau.test;

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {

        int[] arr = { 31, 55, 76, 24, 67, 89, 23, 90, 67, 54, 97, 39, 26, 99, 43, 65, 35 };
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 自底向上归并
     * @param arr
     */
    private static void sort(int[] arr) {

        int[] aux = new int[arr.length]; // 辅助空间
        for (int size = 1; size < arr.length; size *= 2) {
            for (int low = 0; low < arr.length - size; low = low + size + size) {
                System.out.printf("%d\t%d\t%d\n", size, low, Math.min(low + size + size - 1, arr.length));
                merge(arr, aux, low, low + size - 1, Math.min(low + size + size - 1, arr.length-1));
            }
        }
    }

    /**
     * 归并排序：将两个有序数组归并为一个更大的有序数组
     * 
     * 1.空间复杂度为O(n)
     * @param arr
     */
//    private static void sort(int[] arr) {
//
//        int[] aux = new int[arr.length];
//        sort(arr, aux, 0, arr.length - 1);
//    }

    /**
     * 
     * @param arr
     * @param aux 辅助空间
     * @param lo
     * @param hi
     */
    private static void sort(int[] arr, int[] aux, int low, int high) {

        if (high <= low) {
            return;
        }
        int mid = (low + high) / 2;
        sort(arr, aux, low, mid);
        sort(arr, aux, mid + 1, high);
        merge(arr, aux, low, mid, high);
    }

    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {

        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) { // 将arr复制到辅助数组中
            aux[k] = arr[k];
        }

        // 归并 //
        for (int k = low; k <= high; k++) {

            if (i > mid) { // 左半边已耗尽
                arr[k] = aux[j++];
            } else if (j > high) { // 右半边已耗尽
                arr[k] = aux[i++];
            } else if (aux[i] < aux[j]) {
                arr[k] = aux[i++];
            } else {
                arr[k] = aux[j++];
            }
        }
    }
}
